#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// 最大顶点数
#define MAXV 5
// 定义无穷大的值，表示不存在的边
#define INF 0x3f3f3f

/**
 * AOV网和拓扑排序
 * AOV网：有向无环图
 * 过程:
 * 1.找一个没有前驱的节点（即节点入度为0）
 * 2.从网中移除该节点，并且删除从该节点发出的所有边
 * 3.重复1和2，直到图中不存在没有前驱的节点（理论上如果不存在环，最后没有节点）
 */

// 定义边节点（边节点其实存储了边和后一个节点的信息）
typedef struct ArcNode
{
    // 指向节点的索引（通过该做索引可以找到头节点)
    int adjvex;
    // 指向下一个节点
    struct ArcNode *nextarc;
} ArcNode;

// 定义头节点
typedef struct VNode
{
    // 入度
    int count;
    // 指向下一个边节点
    struct ArcNode *firstarc;
} VNode;

// 定义图的邻接表结构体
typedef struct ALGraph
{
    // 顶点数和边数
    int n, e;
    // 顶点邻接表
    struct VNode adjlist[MAXV];
} ALGraph; // 这是一种定义加声明的写法

/**
 * 使用二维数组生成一个图
 * @param graph 图的结构体指针
 * @param A 二维数组
 * @param n 图的顶点数
 */
void createALGraph(ALGraph **graph, int A[][MAXV], int n)
{
    int i, j;

    // 定义一个边节点结构体指针
    ArcNode *p;

    // 动态分配内存
    *graph = (ALGraph *)malloc(sizeof(ALGraph));
    if (*graph == NULL)
    {
        // 内存不足时有可能造成内存分配失败
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }

    // 初始化图
    (*graph)->n = n;
    (*graph)->e = 0;
    for (int i = 0; i < n; i++)
    {
        (*graph)->adjlist[i].count = 0;
        (*graph)->adjlist[i].firstarc = NULL;
    }

    // 添加图中的信息
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // A[i][j]表示i和j之间的边的权值，其实代表了一条边
            if (A[i][j] != 0 && A[i][j] != INF)
            {
                // 创建一个边节点
                p = (ArcNode *)malloc(sizeof(ArcNode));
                if (p == NULL)
                {
                    fprintf(stderr, "malloc error\n");
                    exit(1);
                }
                p->adjvex = j;
                // 增加j的入度
                (*graph)->adjlist[j].count++;
                // 把前一个firstarc链接到当前边节点的nextarc，然后把当前创建的边节点再链接到头节点上
                p->nextarc = (*graph)->adjlist[i].firstarc; // 找到边指向的节点信息，然后找到节点的下一个边节点

                // 将边节点信息链接到头节点上
                (*graph)->adjlist[i].firstarc = p;
                (*graph)->e++; // 边的数量+1
            }
        }
    }
}

void printALGraph(ALGraph *graph)
{
    int i;
    ArcNode *p;
    printf("vertex num: %d , edge num: %d :\n", graph->n, graph->e);
    for (i = 0; i < graph->n; i++)
    {
        printf("%d->", i);
        p = graph->adjlist[i].firstarc;
        while (p != NULL)
        {
            printf("%d->", p->adjvex);
            p = p->nextarc;
        }
        printf("\n");
    }
}

void destroyALGraph(ALGraph *graph)
{
    int i;
    ArcNode *p, *q;
    for (i = 0; i < graph->n; i++)
    {
        p = graph->adjlist[i].firstarc;
        while (p != NULL)
        {
            q = p->nextarc;
            free(p);
            p = q;
        }
    }
    free(graph);
}

bool topSort(ALGraph *graph, int topSeq[])
{
    int n = 0; // topSeq数组的下标
    ArcNode *p;
    int adj;

    int stack[MAXV], top = -1;
    // 找到入度为0的顶点
    for (int i = 0; i < graph->n; i++)
    {
        if (graph->adjlist[i].count == 0)
        {
            stack[++top] = i;
        }
    }
    while (top > -1) // 栈弹空
    {
        // 出栈
        int v = stack[top--];
        topSeq[n] = v;
        n++;
        // 删除v连接的所有边
        p = graph->adjlist[v].firstarc;
        while (p != NULL)
        {
            adj = p->adjvex;
            graph->adjlist[adj].count--;
            if (graph->adjlist[adj].count == 0)
            {
                stack[++top] = adj;
            }
            p = p->nextarc;
        }
    }
    if (n < graph->n)
    {
        // 不是所有的顶点都排序了
        return false;
    }
    else
    {
        return true;
    }
}

int main()
{
    int i, j;
    // 有向图
    int adjMatrix[5][5] = {
        {0, INF, 1, INF, INF},
        {INF, 0, 1, INF, INF},
        {INF, INF, 0, INF, 1},
        {INF, INF, INF, 0, 1},
        {INF, INF, INF, INF, 0},
    };
    printf("5x5 :\n");
    for (i = 0; i < MAXV; i++)
    {
        for (j = 0; j < MAXV; j++)
        {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }

    // 初始化为指针，在函数中动态分配内存
    ALGraph *graph = NULL;
    createALGraph(&graph, adjMatrix, 5);
    printALGraph(graph);

    // topSort
    int topSeq[MAXV];
    memset(topSeq, 0, sizeof(topSeq));
    bool sortedRes = topSort(graph, topSeq);
    // print topSeq
    if (sortedRes)
    {
        printf("sorted\n");
        for (int i = 0; i < MAXV; i++)
        {
            printf("%d ", topSeq[i]);
        }
    }
    else
    {
        printf("unsorted\n");
    }

    destroyALGraph(graph);

    return 0;
}